/*
    TSPClasses - Utility classes for the travelling salesman problem
    Copyright (C) 2011  Laurent Poirrier

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
#include <iostream>
#include <fstream>
#include <string>
#include <cassert>
#include <math.h>
#include "TSPClasses.hpp"

// ***************************************************************************
// generic
// ***************************************************************************
template<typename T>
EdgeData<T>::EdgeData()
	: n(0)
{
}

template<typename T>
EdgeData<T>::EdgeData(int nVertices)
	: n(nVertices), values(nVertices * (nVertices - 1) / 2)
{
}

template<typename T>
EdgeData<T>::EdgeData(const EdgeData &src)
	: n(src.n), values(src.values)
{
}

template<typename T>
EdgeData<T>::~EdgeData()
{
}

template<typename T>
EdgeData<T> &EdgeData<T>::operator=(const EdgeData &src)
{
	n = src.n;
	values = src.values;
	
	return(*this);
}

template<typename T>
void EdgeData<T>::clear()
{
	n = 0;
	values.clear();
}

template<typename T>
void EdgeData<T>::resize(int nVertices)
{
	n = nVertices;
	values.resize(nVertices * (nVertices - 1) / 2);
}

template<typename T>
int  EdgeData<T>::vertices() const
{
	return(n);
}

template<typename T>
int  EdgeData<T>::edges() const
{
	return(values.size());
}

template<typename T>
int  EdgeData<T>::offset(int i, int j) const
{
	if (j > i)
		std::swap(i, j);

	assert(j >= 0);
	assert(i <  n);
	assert(j != i);

	return((i * (i - 1)) / 2 + j);
}

template<typename T>
T &EdgeData<T>::array(int offs)
{
	return(values[offs]);
}

template<typename T>
const T &EdgeData<T>::array(int offs) const
{
	return(values[offs]);
}


template<typename T>
void EdgeData<T>::set(T v)
{
	std::fill(values.begin(), values.end(), v);
}

template<typename T>
void EdgeData<T>::set(int i, int j, T v)
{
	values[offset(i, j)] = v;
}

template<typename T>
T    EdgeData<T>::get(int i, int j) const
{
	return(values[offset(i, j)]);
}

template<typename T>
T   &EdgeData<T>::operator() (int i, int j)
{
	return(values[offset(i, j)]);
}

template<typename T>
T   EdgeData<T>::operator*(const EdgeData &src) const
{
	T v = 0;
	
	assert(values.size() == src.values.size());
	
	for (size_t t = 0; t < values.size(); t++)
		v += values[t] * src.values[t];
	
	return(v);
}

template class EdgeData<double>;
template class EdgeData<int>;
template class EdgeData<char>;

// ***************************************************************************
// TSPModel
// ***************************************************************************
TSPModel::TSPModel()
{
}

TSPModel::TSPModel(int nVertices)
	: EdgeData<double>(nVertices)
{
}

TSPModel::TSPModel(const EdgeData<double> &src)
	: EdgeData<double>(src)
{
}

TSPModel::TSPModel(const TSPModel &src)
	: EdgeData<double>(src)
{
}

TSPModel::~TSPModel()
{
}

TSPModel &TSPModel::operator=(const EdgeData<double> &src)
{
	this->EdgeData<double>::operator=(src);
	return(*this);
}

TSPModel &TSPModel::operator=(const TSPModel &src)
{
	this->EdgeData<double>::operator=(src);
	return(*this);
}

// ***************************************************************************
// TSPSolution
// ***************************************************************************
TSPSolution::TSPSolution()
	: feasible(true)
{
}

TSPSolution::TSPSolution(int nVertices)
	: EdgeData<double>(nVertices), feasible(true)
{
}

TSPSolution::TSPSolution(const EdgeData<double> &sol)
	: EdgeData<double>(sol), feasible(true)
{
}

TSPSolution::TSPSolution(const TSPSolution &sol)
	: EdgeData<double>(sol), feasible(sol.feasible)
{
}

TSPSolution::~TSPSolution()
{
}

TSPSolution &TSPSolution::operator=(const EdgeData<double> &sol)
{
	this->EdgeData<double>::operator=(sol);
	return(*this);
}

TSPSolution &TSPSolution::operator=(const TSPSolution &sol)
{
	this->EdgeData<double>::operator=(sol);
	return(*this);
}



double TSPSolution::getCost(const TSPModel &model) const
{
	return((*this) * model);
}

bool   TSPSolution::isIntegral(double tol) const
{
	for (int i = 0; i < vertices(); i++) {
		for (int j = 0; j < i; j++) {
			if (!isIntegral(i, j, tol))
				return(false);
		}
	}
	
	return(true);
}

bool   TSPSolution::isIntegral(int i, int j, double tol) const
{
	double v = get(i, j);
	
	return(fabs(v - round(v)) <= tol);
}


void   TSPSolution::setFeasible(bool yes)	{ feasible = yes; }
bool   TSPSolution::isFeasible() const		{ return(feasible); }

// ***************************************************************************
// TSPFixing
// ***************************************************************************
TSPFixing::TSPFixing()
{
}

TSPFixing::TSPFixing(int nVertices)
	: EdgeData<char>(nVertices)
{
}

TSPFixing::TSPFixing(const TSPFixing &src)
	: EdgeData<char>(src)
{
}

TSPFixing::~TSPFixing()
{
}

TSPFixing &TSPFixing::operator=(const EdgeData<char> &src)
{
	this->EdgeData<char>::operator=(src);
	return(*this);
}

TSPFixing &TSPFixing::operator=(const TSPFixing &src)
{
	this->EdgeData<char>::operator=(src);
	return(*this);
}

void TSPFixing::unfix()
{
	set(-1);
}

void TSPFixing::fix(int i, int j, bool one)
{
	set(i, j, ((one) ? 1 : 0));
}

void TSPFixing::fix(int i, int j, double zeroone)
{
	set(i, j, ((zeroone > 0.5) ? 1 : 0));
}

void TSPFixing::unfix(int i, int j)
{
	set(i, j, -1);
}

bool TSPFixing::empty() const
{
	return(edges() == 0);
}

bool TSPFixing::isFixed(int i, int j) const
{
	if (empty())
		return(false);
	
	return(get(i, j) != -1);
}

double TSPFixing::fixedValue(int i, int j) const
{
	if (empty())
		return(0.0);
	
	return((get(i, j) == 1) ? 1.0 : 0.0);
}

// ***************************************************************************
// TSPCut
// ***************************************************************************
TSPCut::TSPCut()
	: sense('G'), rhs(0.0)
{
}

TSPCut::TSPCut(int nVertices)
	: EdgeData<double>(nVertices), sense('G'), rhs(0.0)
{
}

TSPCut::TSPCut(const TSPCut &cut)
	: EdgeData<double>(cut), sense(cut.sense), rhs(cut.rhs)
{
}

TSPCut::~TSPCut()
{
}

TSPCut &TSPCut::operator=(const EdgeData<double> &src)
{
	this->EdgeData<double>::operator=(src);
	return(*this);
}

TSPCut &TSPCut::operator=(const TSPCut &src)
{
	this->EdgeData<double>::operator=(src);
	sense = src.sense;
	rhs = src.rhs;
	return(*this);
}


void TSPCut::setSense(char cutType)		{ sense = cutType; }
char TSPCut::getSense() const			{ return(sense); }
void TSPCut::setRHS(double rightHandSide)	{ rhs = rightHandSide; }
double TSPCut::getRHS() const			{ return(rhs); }

double TSPCut::slack(const TSPSolution &sol) const
{
	double lhs;

	lhs = (*this) * sol;
	
	switch(sense) {
	case 'E':
		return(-fabs(lhs - rhs));
	case 'L':
		return(rhs - lhs);
	case 'G':
	default:
		return(lhs - rhs);
	}
}

